HTMLify

class Solution:
    def countSubset(self, arr, k):
        n = len(arr)
        mid = n // 2
        left = arr[:mid]
        right = arr[mid:]
        
        from collections import defaultdict
        
        left_sums = defaultdict(int)
        
        def gen_sums(a, idx, s, mp):
            if idx == len(a):
                mp[s] += 1
                return
            gen_sums(a, idx + 1, s, mp)
            gen_sums(a, idx + 1, s + a[idx], mp)
        
        gen_sums(left, 0, 0, left_sums)
        
        ans = 0
        
        def count_right(a, idx, s):
            nonlocal ans
            if idx == len(a):
                ans += left_sums[k - s]
                return
            count_right(a, idx + 1, s)
            count_right(a, idx + 1, s + a[idx])
        
        count_right(right, 0, 0)
        return ans